﻿//地下城游戏（hard）： https://leetcode.cn/problems/dungeon-game/
class Solution
{
public:
 int calculateMinimumHP(vector<vector<int>>& dungeon) 
 {
 int m = dungeon.size(), n = dungeon[0].size();
 // 建表 + 初始化
 vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
 dp[m][n - 1] = dp[m - 1][n] = 1;
 // 填表
 for(int i = m - 1; i >= 0; i--)
 for(int j = n - 1; j >= 0; j--)
 {
 dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
 dp[i][j] = max(1, dp[i][j]);
 }
 // 返回结果
 return dp[0][0];
 }
};